package com.jwetherell.my.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class TreeUtils {

	public static <T extends Comparable<T>> boolean compareTrees(Node<T> tree1, Node<T> tree2) {
		if (tree1==null && tree2==null)
			return true;
		if (tree1==null || tree2==null)
			return false;
		return (tree1.data==tree2.data) && compareTrees(tree1.left, tree2.left) && compareTrees(tree1.right, tree2.right);
	}
	
	public static <T extends Comparable<T>> void BFS_ZigZag_Iterative(Node<T> root) {

		if (root == null)
			return;

		Stack<Node<T>> cl = new Stack<Node<T>>();
		cl.push(root);
		
		Stack<Node<T>> nl = new Stack<Node<T>>();
		
		boolean LR = true;
		
		Node<T> node;
		while (!cl.isEmpty()) {
			node = cl.pop();
			System.out.print(node + " ");
			
			if (LR) {
				if (node.left != null)
					nl.push(node.left);
				if (node.right != null)
					nl.push(node.right);
			} else {
				if (node.right != null)
					nl.push(node.right);
				if (node.left != null)
					nl.push(node.left);
			}
			
			if (cl.isEmpty()) {
				System.out.println();
				Stack<Node<T>> temp = cl;
				cl = nl;
				nl = temp;
				LR = !LR;
			}
		}
		
	}

	/*
	 * The new node is always inserted as a leaf so the root of the tree
	 * won’t change after any insertion and thus we don’t return root node
	 * from the method.
	 */
	public static <T extends Comparable<T>> void insertIntoBST(Node<T> root, T value) {
		
		if (root == null)
			return;

		if (value == null)
			return;

		int result = root.data.compareTo(value);
		if (result == 1) {
			if (root.left == null) {
				root.left = new Node<T>(value);
				return;
			} else {
				insertIntoBST(root.left, value);
			}
		} else { // if (result == -1 || result == 0)
			if (root.right == null) {
				root.right = new Node<T>(value);
				return;
			} else {
				insertIntoBST(root.right, value);
			}
		}
	}

	public static <T extends Comparable<T>> int minLevel(Node<T> root) {

		if (root == null)
			return -1;

		int minLevel = -1;

		Queue<Node<T>> queue = new LinkedList<Node<T>>();
		queue.add(root);
		queue.add(null); // null is the delimiter to show end of a level

		Node<T> node;
		while (!queue.isEmpty()) {

			node = queue.remove();

			if (node == null) {
				minLevel++;

				if (!queue.isEmpty())
					queue.add(null); // once a level is completed, add 'null' to
										// demarcate the next level (at this
										// point all the nodes of this level
										// have already been put in the queue)

				continue;
			}

			if (node.isLeaf()) {
				return ++minLevel;
			}

			for (Node<T> child : node.getChildren()) {
				queue.add(child);
			}
		}

		return minLevel; // control won't reach here ever because before the
							// queue becomes empty, we must have already found a
							// leaf and thus exited this method from within the
							// while loop itself

	}
	
	public static <T extends Comparable<T>> void assignLevelsToEachNode(Node<T> node, int level) {
		if (node == null)
			return;
		
		node.level = level;
		assignLevelsToEachNode(node.left, node.level + 1);
		assignLevelsToEachNode(node.right, node.level + 1);
	}

	public static <T extends Comparable<T>> int assignHeightsToEachNode(Node<T> node) {
		if (node == null)
			return -1;
		return node.height = Math.max(assignHeightsToEachNode(node.left), assignHeightsToEachNode(node.right)) + 1;
	}
	
	public static <T extends Comparable<T>> int heightOrMaxLevelUsingBFS(Node<T> root) {

		if (root == null)
			return -1;

		int height = -1;

		Queue<Node<T>> queue = new LinkedList<Node<T>>();
		queue.add(root);
		queue.add(null); // null is the delimiter to show end of a level

		Node<T> node;
		while (!queue.isEmpty()) {
			node = queue.remove();

			if (node == null) {
				height++;

				if (!queue.isEmpty())
					queue.add(null); // once a level is completed, add 'null' to
										// demarcate the next level (at this
										// point all the nodes of this level
										// have already been put in the queue)

				continue;
			}

			if (!node.isLeaf()) {
				for (Node<T> child : node.getChildren()) {
					queue.add(child);
				}
			}
		}

		return height;

	}

	/**
	 * DFS is preferred over BFS for finding height
	 * 
	 * @param node
	 * @return
	 */
	public static <T extends Comparable<T>> int heightOrMaxLevelUsingDFS(Node<T> node) {
		if (node == null)
			return -1;

		return Math.max(TreeUtils.heightOrMaxLevelUsingDFS(node.getLeft()), TreeUtils.heightOrMaxLevelUsingDFS(node.getRight())) + 1;
	}

	/**
	 * BFS can be applied to any tree and not just binary tree. That's why we
	 * have used getChildren() instead of leftChild() and rightChild() so that
	 * the function works for any tree
	 * 
	 * @param root
	 */
	public static <T extends Comparable<T>> void BFS_Iterative(Node<T> root) {

		if (root == null)
			return;

		Queue<Node<T>> queue = new LinkedList<Node<T>>();
		queue.add(root);

		Node<T> node;
		while (!queue.isEmpty()) {
			node = queue.remove();
			System.out.print(node.data + " ");
			List<Node<T>> children = node.getChildren();
			if ((children != null) && (!children.isEmpty())) {
				for (Node<T> child : children) {
					queue.add(child);
				}
			}
		}
	}

	// DFS_PreOrder iterative algos
	public static <T extends Comparable<T>> void DFS_PreOrder_Iterative_Left_To_Right(Node<T> root) {
		DFS_PreOrder_Iterative(root, true);
	}
	
	public static <T extends Comparable<T>> void DFS_PreOrder_Iterative_Right_To_Left(Node<T> root) {
		DFS_PreOrder_Iterative(root, false);
	}

	/*
	 * Note: This DFS iterative algo is exactly same as BFS iterative algo except two differences:
	 * 1. instead of Queue, we use Stack here (major difference)
	 * 2. it visit paths from right to left because since we insert children into the stack from
	 * left to right, so while popping up those children they come in reverse order i.e. right to left
	 * order and that's the reason why it visit vertical paths from right to left
	 * So for that, we accept one boolean parameter "leftToRight". If it is true, then we insert children
	 * in right-to-left so while popping up they come in left-to-right order
	 * 
	 * Note: The output is same as PreOrder_Recursive and not In_Order and Post_Order
	 *
	 */
	public static <T extends Comparable<T>> void DFS_PreOrder_Iterative(Node<T> root, boolean leftToRight) {

		if (root == null)
			return;

		Stack<Node<T>> stack = new Stack<Node<T>>();
		stack.add(root);

		Node<T> node;
		while (!stack.isEmpty()) {
			node = stack.pop();
			System.out.print(node.data + " ");
			List<Node<T>> children = node.getChildren();
			if ((children != null) && (!children.isEmpty())) {
				if (leftToRight) { 
					/* to visit from left vertical path to right vertical path 
					 * store the nodes in reverse order i.e. right child first and 
					 * left child second so that left child will come first while popping
					 */
					for (int i = (children.size() - 1); i >= 0; i--) {
						stack.add(children.get(i));
					}
				} else {
					for (Node<T> child : children) {
						stack.add(child);
					}
				}
			}
		}
	}

	/* DFS PreOder, InOrder, and PostOrder recursive algos
	 * UnLike DFS_Iterative, DFS_Recursive uses call-stack (recursion) instead of normal stack
	 */
	public static <T extends Comparable<T>> void DFS_PreOrder_Recursive(Node<T> node) {
		if (node == null)
			return;

		System.out.print(node.data + " ");
		DFS_PreOrder_Recursive(node.left);
		DFS_PreOrder_Recursive(node.right);
	}

	public static <T extends Comparable<T>> void DFS_PostOrder_Recursive(Node<T> node) {
		if (node == null)
			return;

		DFS_PostOrder_Recursive(node.left);
		DFS_PostOrder_Recursive(node.right);
		System.out.print(node.data + " ");
	}

	public static <T extends Comparable<T>> void DFS_InOrder_Recursive(Node<T> node) {
		if (node == null)
			return;

		DFS_InOrder_Recursive(node.left);
		System.out.print(node.data + " ");
		DFS_InOrder_Recursive(node.right);
	}

	
	public static Node<Integer> createBST1() {
		Node<Integer> root = new Node<Integer>(3);
		TreeUtils.insertIntoBST(root, 20);
		TreeUtils.insertIntoBST(root, 1);
		TreeUtils.insertIntoBST(root, 15);
		TreeUtils.insertIntoBST(root, 21);
//		TreeUtils.insertIntoBST(root, 3);
//		TreeUtils.insertIntoBST(root, 12);
//		TreeUtils.insertIntoBST(root, 10);
//		TreeUtils.insertIntoBST(root, 13);
//		TreeUtils.insertIntoBST(root, 18);
//		TreeUtils.insertIntoBST(root, 23);
//		TreeUtils.insertIntoBST(root, 6);
		return root;
	}

	public static Node<Integer> createTree1() {
		Node<Integer> root = new Node<Integer>(2);
		Node<Integer> n11 = new Node<Integer>(7);
		Node<Integer> n12 = new Node<Integer>(5);
		Node<Integer> n21 = new Node<Integer>(2);
		Node<Integer> n22 = new Node<Integer>(6);
		Node<Integer> n23 = new Node<Integer>(9);
		Node<Integer> n31 = new Node<Integer>(5);
		Node<Integer> n32 = new Node<Integer>(8);
		Node<Integer> n33 = new Node<Integer>(4);

		root.left = n11;
		root.right = n12;

		n11.left = n21;
		n11.right = n22;

		n12.right = n23;
		n22.left = n31;
		n22.right = n32;

		n23.left = n33;

		return root;
	}

	// Tree printer
	public static <T extends Comparable<T>> void printTree(Node<T> root) {
		int maxLevel = TreeUtils.printTreemaxLevel(root);
		printNodeInternal(Collections.singletonList(root), 1, maxLevel);
	}

	private static <T extends Comparable<T>> void printNodeInternal(List<Node<T>> nodes, int level, int maxLevel) {
		if (nodes.isEmpty() || TreeUtils.isAllElementsNull(nodes))
			return;

		int floor = maxLevel - level;
		int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
		int firstSpaces = (int) Math.pow(2, (floor)) - 1;
		int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

		TreeUtils.printWhitespaces(firstSpaces);

		List<Node<T>> newNodes = new ArrayList<Node<T>>();
		for (Node<T> node : nodes) {
			if (node != null) {
				System.out.print(node);
				newNodes.add(node.getLeft());
				newNodes.add(node.getRight());
			} else {
				newNodes.add(null);
				newNodes.add(null);
				System.out.print(" ");
			}

			TreeUtils.printWhitespaces(betweenSpaces);
		}
		System.out.println("");

		for (int i = 1; i <= endgeLines; i++) {
			for (int j = 0; j < nodes.size(); j++) {
				TreeUtils.printWhitespaces(firstSpaces - i);
				if (nodes.get(j) == null) {
					TreeUtils.printWhitespaces(endgeLines + endgeLines + i + 1);
					continue;
				}

				if (nodes.get(j).getLeft() != null)
					System.out.print("/");
				else
					TreeUtils.printWhitespaces(1);

				TreeUtils.printWhitespaces(i + i - 1);

				if (nodes.get(j).getRight() != null)
					System.out.print("\\");
				else
					TreeUtils.printWhitespaces(1);

				TreeUtils.printWhitespaces(endgeLines + endgeLines - i);
			}

			System.out.println("");
		}

		printNodeInternal(newNodes, level + 1, maxLevel);
	}

	private static void printWhitespaces(int count) {
		for (int i = 0; i < count; i++)
			System.out.print(" ");
	}

	private static <T> boolean isAllElementsNull(List<T> list) {
		for (Object object : list) {
			if (object != null)
				return false;
		}
		return true;
	}

	private static <T extends Comparable<T>> int printTreemaxLevel(Node<T> node) {
		if (node == null)
			return 0;

		return Math.max(TreeUtils.printTreemaxLevel(node.getLeft()), TreeUtils.printTreemaxLevel(node.getRight())) + 1;
	}
}
